/*
 * Arnoldas Grigutis, MIF INFO 1k. 1gr.
 * Duotas naturinis skaicius k. Raskite k-aji sekos, kuria sudaro is eiles
 * surasyti naturaliuju skaiciu kvadratai, skaitmeni.
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "wraplinux.h"
#include "assert.h"

// Struct for separate one-number integers (squares integers)
typedef struct {
	int alloced;
	int pos;
	int *ints;
} int_arr;

/* Adds a number X to ARR. */
void addto_int_arr(int x, int_arr *arr) {
	if ( arr->pos == arr->alloced ) {
		arr->ints = bpz_realloc(arr->ints, arr->alloced * sizeof(int) * 2);
		arr->alloced = arr->alloced * sizeof(int) * 2;
	}
	//assert(x < 10);
	arr->ints[arr->pos++] = x;
}

/* Returns the length of X. */
int intlen(int x) {
    int len = 1;
    int x_;
    div_t divr;

    x_ = x;

    while ( 1 ) {
        divr = div(x_, 10);
        if( divr.quot == 0 )
            break;
        len++;
        x_ = divr.quot;
    }

    return len;
}

int split_and_add(int x, int_arr *ints)
{
    int len;
    int x_;
    div_t div_;
    int pow_;

    x_ = x;
    len = intlen(x);

    while ( 1 ) {
        if ( intlen(x_) > 1 )
            pow_ = pow(10, intlen(x_) - 1);
        else
            pow_ = 10;

        div_ = div(x_, pow_);
        if ( div_.quot == 0 ) { 
        	//printf("Add1: %d\n", div_.rem);
        	addto_int_arr(div_.rem, ints);
            break; // last number of the integer
        }

        //printf("Add2: %d\n", div_.quot);
        addto_int_arr(div_.quot, ints);
        x_ = x_ - div_.quot * pow_;
    }
    return 0;
}

int
main(int argc, char *argv[])
{
    int_arr ints;
    int_arr sqs;
    int i;
    int k;

	if ( argc != 2 ) {
		fprintf(stderr, "Give k as an argument (k - natural number).\n");
		return 1;
	}
	k = atoi(argv[1]);
	if ( k < 1 ) {
		fprintf(stderr, "Invalid argument k\n");
		return 1;
	}

	// ints.ints will require more size eventually
    sqs.ints = bpz_calloc(k, sizeof(int));
    ints.ints = bpz_calloc(k, sizeof(int));
    sqs.alloced = ints.alloced = k;
    sqs.pos = ints.pos = 0;
    for ( i = 1; i <= k; i++ ) {
    	addto_int_arr(i * i, &sqs);
    }

    for ( i = 0; i < sqs.pos; i++ ) {
        split_and_add(sqs.ints[i], &ints);
    }

    // AND THE MAGIC!
    printf("%d\n", ints.ints[k-1]);

    return 0;
}
